package leecode.test1;

public class Solution {
    public static void main(String[] args) {
        System.out.println("begins");
        int[][] a = new int[100][100];
        A aa = new A();
        System.out.println(aa.step(0, 0, 3, 2));
    }
}

class A {
    private static int[][] cache = new int[100][100];
    private static boolean[][] vsited = new boolean[100][100];

    public static int digui(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        if (m == 0 || n == 0) {
            return 1;
        }
        if (cache[m][n] != 0) {
            return cache[m][n];
        }
        cache[m][n] = digui(m - 1, n) + digui(m, n - 1);
        return cache[m][n];
    }

    public static int dongtaiguihua(int[][] res, int m, int n) {
        res[0][0] = 1;
        for (int i = 0; i <= m; i++) {
            res[i][0] = 1;
        }
        for (int i = 0; i <= n; i++) {
            res[0][i] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                res[i][j] = res[i - 1][j] + res[i][j - 1];
            }
        }
        return res[m][n];
    }

    public int step(int x, int y, int m, int n) {
        if (x < 0 || y < 0 || x > 5 || y > 4) {
            return 0;
        }
        if (x == m && y == n) {
            return 1;
        }
        if (vsited[x][y]) {
            return 0;
        }
        int sum = 0;
        vsited[x][y] = true;
        sum += step(x + 1, y, m, n);
        sum += step(x, y + 1, m, n);
//        sum += step(x-1,y,m,n);
//        sum += step(x,y-1,m,n);
        vsited[x][y] = false;
        return sum;
    }
}